package org.hot100_1;

import org.leetcode.TreeNode;

public class leetcode48 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

       if (root==null){
           return null;
       }

       if (root==p || root==q){
           return root;
       }

       //如果当前的节点既不等于p也不等于q，并且不为null，那么需要递归判断这个节点的左子树和右子树是否存在p和q

        //后序遍历
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        //中:对左子树和右子树返回的结果进行判断
        if (left!=null && right!=null){
            return root;
        }else if (left==null && right!=null){
            return right;
        }else if (left!=null && right==null){
            return left;
        }else {
            return null;
        }
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {

        if (root==p ||root==q){
            return root;
        }

        if (root==null){
            return null;
        }

        TreeNode leftNode = lowestCommonAncestor2(root.left, p, q);
        TreeNode rightNode = lowestCommonAncestor2(root.right, p, q);

        if (leftNode!=null && rightNode!=null){
            return root;
        }else if (leftNode==null && rightNode!=null){
            return rightNode;
        }else if (leftNode!=null && rightNode==null){
            return leftNode;
        }else {
            return null;
        }

    }
}
